import collections


class Solution(object):
    def maxStudents(self, seats):
        m = len(seats)
        n = len(seats[0])
        now = collections.defaultdict(int)

        def judge(val, last_val):
            for j in range(n):
                if (val >> j) & 1:
                    if (last_val >> (j + 1)) & 1 == 0 and (j == 0 or (last_val >> (j - 1)) & 1 == 0):
                        continue
                    else:
                        return False
            return True

        for val in range(1 << n):
            flag = True
            for j in range(n):
                if (val >> j) & 1:
                    if seats[0][j] == '.':
                        if j == 0 or (val >> (j - 1)) & 1 == 0:
                            continue
                        else:
                            flag = False
                            break
                    else:
                        flag = False
                        break
            if flag:
                now[val] = val.bit_count()
        for i in range(1, m):
            next_st = collections.defaultdict(int)
            for val in range(1 << n):
                flag = True
                for j in range(n):
                    if (val >> j) & 1:
                        if seats[i][j] == '.':
                            if j == 0 or (val >> (j - 1)) & 1 == 0:
                                continue
                            else:
                                flag = False
                                break
                        else:
                            flag = False
                            break
                if flag:
                    for last_val in now:
                        if judge(val, last_val):
                            next_st[val] = max(next_st[val], val.bit_count() + now[last_val])
            now = next_st
        return max(list(now.values()))


data = Solution()
# seats = [["#", ".", "#", "#", ".", "#"], [".", "#", "#", "#", "#", "."], ["#", ".", "#", "#", ".", "#"]]
# print(data.maxStudents(seats))
seats = [[".", "#"], ["#", "#"], ["#", "."], ["#", "#"], [".", "#"]]
print(data.maxStudents(seats))
